import java.util.*;

/**
 * 面试题 16.19. 水域大小
 * https://leetcode-cn.com/problems/pond-sizes-lcci/
 */
public class Solutions_mianshi_16_19 {
    public static void main(String[] args) {
        int[][] land = {{0, 2, 1, 0},
                        {0, 1, 0, 1},
                        {1, 1, 0, 1},
                        {0, 1, 0, 1}};  // output: {1, 2, 4}

        int[] result = pondSizes(land);
        System.out.println(Arrays.toString(result));
    }

    private static int row = 0, col = 0;
    private static int[][] direct = null;
    public static int[] pondSizes(int[][] land) {
        List<Integer> list = new ArrayList<>();
        // 上、下、左、右、左上、右上、左下、右下，八个方向的索引移动
        direct = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1},
                             {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
        row = land.length;
        col = land[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (land[i][j] == 0) {
                    // 接收搜索的结果，添加到 list 列表中
                    int count = dfs(land, i, j, 0);
                    list.add(count);
                }
            }
        }
        int size = list.size();
        if (size == 0) {
            return new int[0];
        }
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = list.get(i);
        }
        // 升序排列
        Arrays.sort(res);
        return res;
    }

    public static int dfs(int[][] land, int i, int j, int count) {
        land[i][j] = -1;
        for (int[] dir : direct) {
            // 搜索八个方向上的 0 的个数，相加
            int m = i + dir[0];
            int n = j + dir[1];
            if (m < 0 || n < 0 || m >= row || n >= col || land[m][n] != 0) {
                // 不满足条件时，不进行搜索
                continue;
            }
            count += dfs(land, m, n, 0);
        }
        // 八个方向上的 0 的个数，加上 land[i][j] 上的 1 个 0
        return count + 1;
    }
}
